# @author : sentry
# @since : 2023-09-12
# 有效的括号

"""
给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
示例：{[()]}
"""


# 方法一 字符串替换法
def valid_str(string):
    if len(string) % 2 == 1:
        return False
    while '()' in string or '[]' in string or '{}' in string:
        string = string.replace('()', '')
        string = string.replace('[]', '')
        string = string.replace('{}', '')
    return string == ''


print(valid_str('()'))  # True
print(valid_str('()[]{}'))  # True
print(valid_str('()[]{[()]}'))  # True
print(valid_str('()[]{[(}]}'))  # False

print('=' * 40)


# 方法二 栈
def valid_str_stack(string):
    if len(string) % 2 == 1:
        return False
    stack = []
    char_dict = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    for char in string:
        if char in char_dict:
            # 右括号
            if not stack or char_dict[char] != stack.pop():
                return False
        else:
            # 左括号
            stack.append(char)
    return not stack


print(valid_str_stack('(){}[({[]})]'))  # True
print(valid_str_stack('(){}[({[)})]'))  # False
print(valid_str_stack(''))  # True
